package baseclass.a_sort.mergeSort;


import baseclass.a_sort.ArraysTool;

/**
 * @date 2020/2/26 19:35
 */
public class MergeSort {
    public static void merge(int[] arr) {
        if (!ArraysTool.check(arr)) return;
        process(arr, 0, arr.length - 1);
    }

    private static void process(int[] arr, int l, int r) {
        if (l >= r) return;
        int mid = l + (r - l) / 2;
        process(arr, l, mid);
        process(arr, mid + 1, r);
        doMerge(arr, l, mid, r);
    }

    private static void doMerge(int[] arr, int l, int mid, int r) {
        int[] help = new int[r - l + 1];
        int p1 = l;
        int p2 = mid + 1;
        int index = 0;
        while (p1 <= mid && p2 <= r) {
            help[index++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1 <= mid) {
            help[index++] = arr[p1++];
        }
        while (p2 <= r) {
            help[index++] = arr[p2++];
        }
        for (int i = 0; i < help.length; i++) {
            arr[l + i] = help[i];
        }
    }
}
